﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。
给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对  109 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

 

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。
*/

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int maxSumMinProduct(int* nums, int numsSize) {
    int n = numsSize;
    int arr[n + 2];
    long preSum[n + 2];
    int i;
    long res = 0;
    long mult;
    int stack[n + 2];
    int top = 0;

    /* 数组左右补0, 方便求左右更小值 */
    arr[0] = 0;
    arr[n + 1] = 0;
    for (i = 1; i <= n; i++) {
        arr[i] = nums[i - 1];
    }

    /* 前缀和 */
    preSum[0] = 0;
    for (i = 1; i < n + 2; i++) {
        preSum[i] = preSum[i - 1] + arr[i];
    }

    /* 单调栈, 遇到小于栈顶的数, 处理栈顶元素 */
    for (i = 0; i < n + 2; i++) {
        while (top > 0 && arr[i] < arr[stack[top - 1]]) { /* 当前元素小于栈顶元素 */
            top--;
            mult = arr[stack[top]] * (preSum[i - 1] - preSum[stack[top - 1]]); /* 前缀和求区间和 */
            res = MAX(res, mult);
        }
        stack[top++] = i;
    }
    return res % 1000000007;
}